package mine.code.question.动态规划;

import org.junit.Test;

/**
 * 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
 * <p>
 * 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
 * <p>
 * 示例 1:
 * <p>
 * 输入: "abc"
 * 输出: 3
 * 解释: 三个回文子串: "a", "b", "c".
 * abccba
 *
 * @author caijinnan
 * @date 2020/3/25 10:47
 */
public class 回文子串 {

    @Test
    public void run() {
        String s = "aaa";
        System.out.println(countSubstrings(s));
    }

    /**
     * aabaaba
     */
    public int countSubstrings(String s) {
        char[] charArr = new char[s.length() * 2 + 1];
        for (int i = 0; i < s.length(); i++) {
            charArr[2 * i] = '#';
            charArr[2 * i + 1] = s.charAt(i);
        }
        charArr[charArr.length - 1] = '#';
        int sum = 0;
        int maxRight = 0;
        int center = 0;
        int[] rLength = new int[charArr.length];
        for (int i = 0; i < charArr.length; i++) {
            rLength[i] = i >= maxRight ? 1 : Math.min(rLength[2 * center - i], maxRight - i);
            while (true) {
                int left = i - rLength[i];
                int right = i + rLength[i];
                if (left < 0 || right > charArr.length - 1 || charArr[right] != charArr[left]) {
                    break;
                }
                rLength[i]++;
            }
            if (i + rLength[i] > maxRight) {
                maxRight = i + rLength[i];
                center = i;
            }
            sum += (rLength[i] - 1) / 2;
        }
        return sum + s.length();
    }


}
